package leetcode

import kotlinetc.println

//https://leetcode.com/problems/permutations-ii/
/**
 * [permuteRecursive] 没有考虑重复情况；
 * 这里的全排列需要考虑数字重复
 */
fun main(args: Array<String>) {

    permuteUnique(intArrayOf(3, 3, 0, 3)).println()
}

fun permuteUnique(nums: IntArray): List<List<Int>> {

    val result = ArrayList<List<Int>>()
    val used = Array(nums.size, { false })
    nums.sort()
    permuteUniqueRecursive(nums, used, arrayListOf(), result)
    return result
}

fun permuteUniqueRecursive(nums: IntArray, used: Array<Boolean>, tmp: ArrayList<Int>, result: ArrayList<List<Int>>) {
    if (tmp.size == nums.size) {
        result.add(ArrayList(tmp))
    } else {
        for (i in 0 until nums.size) {
            if (used[i]) continue
            //如果前一个数字用过并且和当前数字相同那么跳过，这样去除重复排列
            //例如 [a1,a2]  a1=a2 =1 ,最后输出的[1,1]实际是[a2,a1]，
            //也就是说前面的数字是没有机会排到前面的，都是后面的数字排前面
            if (i - 1 >= 0 && nums[i - 1] == nums[i] && used[i - 1]) continue
            used[i] = true
            tmp.add(nums[i])
            permuteUniqueRecursive(nums, used, tmp, result)  //1
            tmp.removeAt(tmp.lastIndex) //如果1是最后一次递归，那么递归完之后回到这里就移除掉最后一个，下次循环添加另一个
            used[i] = false
        }
    }
}
